//寻找二叉树是否存在路径总和为某一个数
//递归或迭代都可实现，使用的是前序遍历和回溯

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
};


//递归法
//思路是count减到0说明有路径总和sum
bool traversal(TreeNode* cur,int count)
{
    if(!cur->left&&!cur->right&&count==0) return true;
    if(!cur->left&&!cur->right) return false;

    if(cur->left)
    {
        count-=cur->left->val;
        if(traversal(cur->left,count)) return true;
        count+=cur->left->val;  //回溯的体现：撤销处理结果
    }

    if(cur->right)
    {
        count-=cur->right->val;
        if(traversal(cur->right,count)) return true;
        count+=cur->right->val;
    }
    return false;
}
bool hasPathSum_recursion(TreeNode* root,int sum)
{
    if(!root) return false;
    return traversal(root,sum-root->val);//遍历时没有减掉root的，所以传入的是sum-root->val
}


//迭代法
//实现原理跟求路径差不多，不过使用了pair来储存多个路径
//还是使用栈来模拟递归
#include <stack>
#include <utility>
using std::pair;
using std::stack;
bool hasPathSum(TreeNode* root,int targetSum)
{
    if(!root) return false;
    stack<pair<TreeNode*,int>> st;
    st.push(pair<TreeNode*,int>(root,root->val));//传入pair方法
    while(!st.empty())
    {
        pair<TreeNode*,int> node=st.top();
        st.pop();
        //first是指针，second是节到达该节点的路径总值
        if(!node.first->left&&!node.first->right&&node.second==targetSum) return true;


        //右子树先入栈
        if(node.first->right){
            st.push(pair<TreeNode*,int>(node.first->right,
            node.second+node.first->right->val));
        }

        if(node.first->left){
            st.push(pair<TreeNode*,int>(node.first->left,
            node.second+node.first->left->val));
        }

    }
    return false;
}